P5929 [POI1999]地图

发布于 2020-11-25 | 分类于 dp | 3分钟 | 480字数

至少有一半不小于 $A(k)$ , 至少有一半不大于 $A(k)$

所以 $A(k)$ 应该是选出的区域人口的中位数。

为了使误差尽可能小，每次应该取排序后连续的一段区间染相同颜色。

阅读全文 »

CF757E Bash Plays with Functions

发布于 2020-11-25 | 分类于数论 | 4分钟 | 635字数

根据题意进行分类讨论：

令 $\tau(n)$ 为 $n$ 的不同质因数的个数。

阅读全文 »

SP4060 KPGAME - A game with probability

发布于 2020-11-25 | 分类于博弈论、概率dp | 5分钟 | 720字数

$dp[0/1][i]$ :有 $i$ 颗石子 Alice/Bob 为先手，Alice 赢的概率

令 $P$ 为 Alice 拿走石子的概率， $Q$ 为 Bob 拿走石子的概率。

\begin{cases}

阅读全文 »

P1560 [USACO5.2]蜗牛的旅行

发布于 2020-10-14 | 分类于搜索 | 3分钟 | 465字数

这道题是一道典型的搜索题，我们用

dfs(x,y,step,s)

表示蜗牛在

(x,y)

这个点，走了

step

步，当前的方向（起点的

s=0

，特殊处理一下）。

当蜗牛确定一个方向后，我们就不断让它前进，同时记录它走过的格子，直到它遇到障碍，出界或者到达已走过的点停止。

如果蜗牛遇到障碍，我们就枚举每个方向，因为前方有障碍，后方已经走过，所以蜗牛只会向左或向右转，不需要特殊处理。

阅读全文 »

P2894 [USACO08FEB]酒店Hotel

发布于 2020-10-14 | 分类于线段树 | 5分钟 | 963字数

这道题明显是线段树的板题，至于考试时因为懒标记的小问题只有20分，~~我也很无奈~~。

进入正题，既然要修改查询区间内连续的一段元素，~~似曾相识的感觉~~。
我们等价的把空房子看为1，住人的房子看为0。

阅读全文 »

CF39A C*++ Calculations

发布于 2020-10-14 | 分类于贪心 | 4分钟 | 729字数

题意简述

给你一个含变量 $x$ 的式子，所有 $x$ 的系数为常数，定义模糊的部分按任意次序计算。如: $a+++++a$ 既可以先算 $a++$ , 也可以先算 $++a$ 。

给你 $a$ 的初值，求算式的最大值。

阅读全文 »

P5427 [USACO19OPEN]Left Out

发布于 2020-10-14 | 4分钟 | 707字数

为了书写方便，我们将 $'L'$ 表示为0， $'R'$ 表示为1。

现在题目转化为给你一个01矩阵，每次可将一行或一列的01反转，要求最后只有一个1或只有一个0，问能否办到。

现在，我们将第一行和第一列的元素全变为1（0也可以），这个很好办到，翻转第一行的元素就将该元素所在列翻转，列同理。

阅读全文 »

P5017 摆渡车

发布于 2020-10-14 | 分类于斜率优化 | 8分钟 | 1416字数

这道题我们先看一下数据范围: $n≤500,m≤100,0≤t_i≤4×10^6$

显然复杂度和 $n,m$ 有关，既然如此，我们考虑用 $t$ 的复杂度来解决此题吧。（此题解法不止一种）

我们用 $dp[i]$ 表示在 $i$ 时刻发车（不管是第几次），所有在 $i$ 时刻之前到达的人的等待时间之和。 $tot[i]$ 表示第 $i$ 时刻有多少人开始等车，显然有：

阅读全文 »

CF45G Prime Problem

发布于 2020-10-14 | 分类于数学 | 2分钟 | 392字数

前置知识：哥德巴赫猜想：任一大于2的偶数都可写成两个质数之和

~~然后，这道题就非常水了。~~

令 $S=1+2+...+n$ , 我们分类讨论 $S$ 的情况就好了。

阅读全文 »

P3232 [HNOI2013]游走

发布于 2020-10-14 | 分类于期望dp 、高斯消元 | 4分钟 | 641字数

这道题边的数量最高是10000多，而点只有500，这提醒我们，我们不能直接对边求期望，而是点。

设 $Expection[u]$ 表示点 $u$ 的期望走过次数， $Degree[u]$ 表示点 $u$ 的度数。

那么，

阅读全文 »